/**
 * 
 */
package com.gwcloud.leetcode.tags.dp;

/**
 * @ClassName   : Leetcode0650 
 * @author      : ganwei 
 * @date        : 2020年5月16日
 * @Description : Leetcode0650 只有两个键的键盘
 */
public class Leetcode0650 {
    /**
     * -解题思路，动态规划
     */
	public int minSteps(int n) {
		//dp表示i个字符至少要进行多少次操作
		int[] dp = new int[n+1];
		int h = (int) Math.sqrt(n);
		for(int i = 2; i <= n; i++) {
			dp[i] = i;
			for(int j = 2; j <= h ; j++) {
				if(i % j == 0) {
					dp[i] = dp[j] + dp[i/j];
					break;
				}
			}
		}
		
		return dp[n];
    }
	
	public void printdp(int[] dp) {
		for(int i = 0; i < dp.length; i++) {
			System.out.print(dp[i]);
			System.out.print(" ");
		}
	}
	
	/**
	 * -主函数
	 */
	public static void main(String[] args){
		Leetcode0650 l0650 = new Leetcode0650();
		//l0650.minSteps(5);
		System.out.println(l0650.minSteps(9));
	}
}
